//
//  main.cpp
//  LinearityDemo
//
//  Created by 李禹 on 15/5/24.
//  Copyright (c) 2015年 dayu. All rights reserved.
//

#include <iostream>
#include "Linearity.h"
#include "CommonFunction.h"

void MergeList(SqList La, SqList Lb, SqList &c);
void Union(SqList &La, SqList Lb);
void Intersection(SqList La, SqList Lb, SqList &c);
void testList();
void testMergeList();
void testUnion();
void testIntersection();

Status sq(ElemType c1, ElemType c2) {
    return c1 == c2*c2;
}

void db1(ElemType &c) {
    c *= 2;
}

int main(int argc, const char * argv[]) {

//    testList();
//    testMergeList();
//    testUnion();
    testIntersection();
    return 0;
}

void testList() {
    SqList sqList;
    InitList(sqList);
    
    for (int i=1; i <= 5; i++) {
        ListInsert(sqList, 1, i);
    }
    printf("初始化L后，L.length = %zd, L.listsize = %zd, L.elem = %zd\n", sqList.length, sqList.listsize, sqList.elem);
    ListTraverse(sqList, print1);
    
    Status i = ListEmpty(sqList);
    printf("L.length = %d(改变), L.listsize = %d(不变)\n", sqList.length, sqList.listsize);
    printf("L.elem = %zd(不变), L是否为空? i = %zd(1:是, 0:否)\n", sqList.elem, i);
    
    ClearList(sqList);
    i = ListEmpty(sqList);
    printf("L.length = %d(改变), L.listsize = %d(不变)\n", sqList.length, sqList.listsize);
    printf("L.elem = %zd(不变), L是否为空? i = %zd(1:是, 0:否)\n", sqList.elem, i);
    
    for (int i = 1; i <= 10; i++) {
        ListInsert(sqList, i, i);
    }
    ListTraverse(sqList, print1);
    printf("L.length = %d(改变), L.listsize = %d(不变)\n", sqList.length, sqList.listsize);
    ListInsert(sqList, 1, 0);
    printf("L.length = %d(改变), L.listsize = %d(改变), L.elem = %zd(有可能改变)\n", sqList.length, sqList.listsize, sqList.elem);
    
    ElemType e;
    GetElem(sqList, 5, e);
    print(e);
    printf("\n");
    i = 10;
    for (; i <= 11; i++) {
        int k = LocateElem(sqList, i, equal);
        if (k) {
            printf("第%d个元素的值为%d\n", k, i);
        }else {
            printf("没有值为%d的元素\n", i);
        }
    }
    
    for (i = 3; i <= 4; i++) {
        int k = LocateElem(sqList, i, sq);
        k ? printf("第%d个元素的值为%d的平方\n", k, i) : printf("没有值为%d的元素\n", i);
    }
    
    ElemType e0;
    for (i = 1; i <= 2; i++) {
        GetElem(sqList, i, e0);
        printf(" i = %d", i);
        printf(" length = %d", ListLength(sqList));
        int j = PriorElem(sqList, e0, e);
        j == ERROR ? printf("元素%d无前驱\n", e0) : printf("元素%d的前驱为%d\n", e0, e);
    }
    
    for (i = ListLength(sqList) - 1; i <= ListLength(sqList); i++) {
        GetElem(sqList, i, e0);
        int j = NextElem(sqList, e0, e);
        j == ERROR ? printf("元素%d无后继\n", e0) : printf("元素%d的后继为%d\n", e0, e);
    }
    
    int length = ListLength(sqList);
    for (i = length+1; i >= length; i--) {
        Status status = ListDelete(sqList, i, e);
        status == ERROR ? printf("删除第%d个元素失败\n", i) : printf("删除第%d个元素成功，其值为%d\n", i, e);
    }
    printf("length = %d\n", ListLength(sqList));
    
    ListTraverse(sqList, db1);
    printf("L的元素值加倍后，L = ");
    ListTraverse(sqList, print1);
    
    DestoryList(sqList);
    i = ListEmpty(sqList);
    printf("销毁L后, L.length = %d(改变), L.listsize = %d(改变)\n", sqList.length, sqList.listsize);
    printf("L.elem = %zd(改变), L是否为空? i = %zd(1:是, 0:否)\n", sqList.elem, i);

}

void testMergeList() {
    SqList La, Lb, Lc;
    int j;
    InitList(La);
    for (j = 1; j <= 5; j++) {
        ListInsert(La, j, j);
    }
    printf("La = ");
    ListTraverse(La, print1);
    InitList(Lb);
    for (j = 1; j <= 10; j++) {
        ListInsert(Lb, j, j*2);
    }
    printf("Lb = ");
    ListTraverse(Lb, print1);
    MergeList(La, Lb, Lc);
    
    printf("Lc = ");
    ListTraverse(Lc, print1);
}

void testUnion() {
    SqList La, Lb;
    int j;
    InitList(La);
    for (j = 1; j <= 5; j++) {
        ListInsert(La, j, j);
    }
    printf("La = ");
    ListTraverse(La, print1);
    InitList(Lb);
    for (j = 1; j <= 10; j++) {
        ListInsert(Lb, j, j*2);
    }
    printf("Lb = ");
    ListTraverse(Lb, print1);
    Union(La, Lb);
    
    printf("La = ");
    ListTraverse(La, print1);
}

void testIntersection() {
    SqList La, Lb, Lc;
    int j;
    InitList(La);
    for (j = 1; j <= 30; j++) {
        ListInsert(La, j, j);
    }
    printf("La = ");
    ListTraverse(La, print1);
    InitList(Lb);
    for (j = 1; j <= 15; j++) {
        ListInsert(Lb, j, j*2);
    }
    printf("Lb = ");
    ListTraverse(Lb, print1);
    
    Intersection(La, Lb, Lc);
    
    printf("Lc = ");
    ListTraverse(Lc, print1);
    printf("Lc.length = %d, Lc.listsize = %d\n", Lc.length, Lc.listsize);
}

void MergeList(SqList La, SqList Lb, SqList &Lc) {
    ElemType *pa, *pa_last, *pb, *pb_last, *pc;
    pa = La.elem;
    pb = Lb.elem;
    Lc.listsize = Lc.length = La.length + Lb.length;
    pc = Lc.elem = (ElemType *)malloc(Lc.listsize * sizeof(ElemType));
    if (!Lc.elem) {
        exit(OVERFLOW);
    }
    pa_last = pa + ListLength(La) - 1;
    pb_last = pb + ListLength(Lb) - 1;
    while (pa <= pa_last && pb <= pb_last) {
        if (*pa <= *pb) {
            *pc++ = *pa++;
        }else {
            *pc++ = *pb++;
        }
    }
    while (pa <= pa_last) {
        *pc++ = *pa++;
    }
    while (pb <= pb_last) {
        *pc++ = *pb++;
    }
}

void Union(SqList &La, SqList Lb) {
    ElemType e;
    int La_len, Lb_len;
    int i;
    La_len = ListLength(La);
    Lb_len = ListLength(Lb);
    for (i = 1; i <= Lb_len; i++) {
        GetElem(Lb, i, e);
        if (!LocateElem(La, e, equal)) {
            ListInsert(La, ++La_len, e);
        }
    }
}

void Intersection(SqList La, SqList Lb, SqList &Lc) {
    ElemType e;
    int La_len, Lb_len;
    int i, j=1;
    La_len = ListLength(La);
    Lb_len = ListLength(Lb);
    InitList(Lc);
    for (i = 1; i <= Lb_len; i++) {
        GetElem(Lb, i, e);
        if (LocateElem(La, e, equal)) {
            ListInsert(Lc, j++, e);
        }
    }
}
